#include <stdio.h>
#include <stdlib.h>

#define NUM 10
typedef struct node
{
    int data;          // 存数据
    struct node *next; // 存指针
} Hash;

typedef struct
{
    int num;
    Hash *hash[];
} hash_table;

int hash_init(Hash *p_hash[], int num)
{
    for (int i = 0; i < num; i++)
    {
        p_hash[i] = (Hash *)malloc(sizeof(Hash));
        p_hash[i]->next = NULL;
    }

    return 0;
}

hash_table *hash_tablle_init(int num)
{
    hash_table *t = calloc(1, sizeof(int) + sizeof(Hash *) * num);
    if (t == NULL)
    {
        perror("calloc");
        exit(EXIT_FAILURE);
    }
    t->num = num;
    hash_init(t->hash, num);

    return t;
}

int hash_table_easy_show(hash_table *p_hash_table)
{
    int num = p_hash_table->num;
    int i;
    for (i = 0; i < num; i++)
    {
        printf("h[%d]=%p\n", i, (void *)p_hash_table->hash[i]);
    }
    return 0;
}

int hash_insert(hash_table *h_table, const int data)
{
    int index = data % h_table->num;
    Hash *p_index = h_table->hash[index];
    Hash *p_new = (Hash *)malloc(sizeof(Hash));
    p_new->data = data;
    p_new->next = p_index->next;
    p_index->next = p_new;

    return 0;
}

int hash_show(hash_table *h_table)
{
    for (int i = 0; i < h_table->num; i++)
    {
        Hash *p_index = h_table->hash[i];
        printf("key[%d]: ", i);
        while (p_index->next != NULL)
        {
            printf("%d ", p_index->next->data);
            p_index = p_index->next;
        }
        printf("\n");
    }

    return 0;
}

int hash_search(hash_table *h_table, const int key)
{
    int index = key % h_table->num;
    Hash *p_index = h_table->hash[index];
    while (p_index->next != NULL)
    {
        if (p_index->next->data == key)
        {
            printf("key[%d]=%d\n", index, p_index->next->data);
            return 1;
        }
        p_index = p_index->next;
    }

    return 0;
}

int hash_table_free(hash_table *table)
{
    int i;
    for(i=0;i<table->num;i++)
    {
        Hash *index = table->hash[i];
        while(index->next != NULL)
        {
            Hash *tmp = index->next;
            index->next = tmp->next;
            free(tmp);
            tmp = NULL;
        }
        free(index);
    }
    free(table);

    return 0;
}

int main(void)
{
    hash_table *p_hash_table = hash_tablle_init(NUM);
    hash_table_easy_show(p_hash_table);
    int a[11] = {100, 34, 14, 45, 46, 98, 68, 69, 7, 31, 26};
    int i;
    int a_len = sizeof(a) / sizeof(a[0]);

    // hash 添加
    for (i = 0; i < a_len; i++)
    {
        hash_insert(p_hash_table, a[i]);
    }
    // hash 遍历
    hash_show(p_hash_table);

    // hash 搜索
    int b[11] = {105, 34, 22, 45, 64, 98, 68, 99, 7, 85, 26};
    int b_len = sizeof(b) / sizeof(b[0]);
    int ret;
    for (i = 0; i < b_len; i++)
    {
        ret = hash_search(p_hash_table, b[i]);
        if (ret){
            printf("find key=%d\n",b[i]);
        }
        else{
            printf("not find key=%d\n",b[i]);
        }
    }

    hash_table_free(p_hash_table);

    return 0;
}